class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

// 创建根节点
const root = new TreeNode("A");

// 创建第二层节点
root.left = new TreeNode("B");
root.right = new TreeNode("C");

// 创建第三层节点
root.left.left = new TreeNode("D");
root.left.right = new TreeNode("E");
root.right.left = new TreeNode("F");
root.right.right = new TreeNode("G");

// 创建第四层节点
root.left.left.left = new TreeNode("H");
root.left.left.right = new TreeNode("I");

//1.递归写法
// var inorderTraversal = function(root) {
//     if(root===null) return [];
//     let leftRes=inorderTraversal(root.left)
//     let rightRes=inorderTraversal(root.right)
//     return [...leftRes,root.val,...rightRes]
// };


//2.迭代写法
var inorderTraversal = function(root) {
    if (root === null) return [];  // 空树直接返回空数组
    let res = [];          // 用于存储结果（中序遍历顺序的节点值）
    let nodeStack = [];    // 模拟递归调用栈，用来存储还没处理的节点
    // 一直处理，直到所有节点都处理完（root为空，栈也为空）
    while (root || nodeStack.length > 0) {
        // 一直往左子树走，把沿路的节点都压入栈
        // 为什么要额外加循环？因为对于每一个节点，一定是找到他最左边的子节点才开始处理
        while (root) {
            nodeStack.push(root);  // 将当前节点压栈，稍后回溯处理
            root = root.left;      // 继续往左走
        }
        // 当前节点已经没有左子节点了
        root = nodeStack.pop();    // 从栈中取出最近压入的节点（左子树处理完后回到它）
        res.push(root.val);        // 访问这个节点（根）

        root = root.right;         // 然后去处理右子树（可能继续入栈）
    }
    return res;
};

console.log(inorderTraversal(root));
